/*什么是基数排序：通过关键字进行分发之后在回收。在回收时需要先入先出的原则
      以扑克牌为例，有花色：核桃，红桃，方块，桃花。加数字。先以花色进行分类时就可以得到4组以花色进行排列的队列，再回收连续的必然是同一种花色
      再以数字分类得到2~A的13个队列，相同的数字在同一个队列，再回收时就可以得到从2开始排列，并且相同的花色还在一起，

1.MSD:最高位优先。
      比如数字258，就从白位开始分发，在十位分发...
2.LSD:最低位优先
      比如数字258，就先从个位开始风法，在十位分发...

*/


#include <iostream>
#include <queue>
#include <stdio.h>

#define K 3
#define RADIX 10

std::queue<int> q[RADIX];

int Kzhi(int value, int k)
{
	int key = 0;
	while (k >= 0)
	{
		key = value % 10;
		value /= 10;
		k--;
	}
	return key;
}
void FenFa(int ar[],int left,int right,int k)
{
	for (int i = left; i < right; i++)
	{
		int key = Kzhi(ar[i], k);
		q[key].push(ar[i]);
	}
}
void HuiSou(int ar[])
{
	int key = 0;
	for (int i = 0; i < RADIX; i++)
	{
		while (!q[i].empty())
		{
			ar[key++] = q[i].front();
			q[i].pop();
		}
	}
}
void RadixSort(int ar[], int left, int right)
{
	for (int i = 0; i < K; i++)//以数字的个位，十位，白位当关键字进行分发
	{
		//分发
		FenFa(ar, left, right, i);
		//回收
		HuiSou(ar);
	}
}
int main()
{
	int ar[] = { 278,109,63,930,589,184,505,269,8,83 };
	int n = sizeof(ar) / sizeof(ar[0]);
	
	for (int i = 0; i < n; i++)
	{
		printf("%d ", ar[i]);
	}
	printf("\n");
	RadixSort(ar, 0, n);
	
	for (int i = 0; i < n; i++)
	{
		printf("%d ", ar[i]);
	}
		return 0;
}
